Graphes et matrices - Expert

Matrice d'adjacence d'un graphe

Exercice 1 : Distance entre deux sommets d'un graphe non orienté.

On considère le graphe non orienté ci-dessous.


Déterminer la distance entre le sommet \(A\) et le sommet \(E\).

Exercice 2 : Déterminer une matrice d'adjacence et des chemins

On considère le graphe non orienté ci-dessous.



Déterminer la matrice d'adjacence de ce graphe en ordonnant les sommets dans l'ordre alphabétique.
Quel est le nombre de chemins de longueur 3 partant de E ?
Quel est le nombre de chemins de longueur 4 allant de G à B ?

Exercice 3 : Déterminer depuis une matrice si le graphe associé est orienté.

Parmi les matrices suivantes, sélectionner celles dont le graphe associé est orienté.

  • 1.\(\begin{pmatrix}0 & 0 & 1 & 0 & 0\\1 & 0 & 0 & 0 & 0\\1 & 0 & 0 & 1 & 1\\0 & 0 & 0 & 0 & 1\\0 & 1 & 1 & 1 & 0\end{pmatrix}\)
  • 2.\(\begin{pmatrix}0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 1 & 1\\1 & 0 & 0 & 0 & 1\\0 & 1 & 0 & 0 & 1\\1 & 0 & 0 & 0 & 0\end{pmatrix}\)
  • 3.\(\begin{pmatrix}0 & 0 & 1 & 0 & 1\\0 & 0 & 0 & 1 & 0\\1 & 0 & 0 & 1 & 1\\0 & 1 & 1 & 0 & 1\\1 & 0 & 1 & 1 & 0\end{pmatrix}\)
  • 4.\(\begin{pmatrix}0 & 0 & 0 & 1 & 1\\0 & 0 & 1 & 1 & 0\\0 & 1 & 0 & 1 & 0\\1 & 1 & 1 & 0 & 0\\1 & 0 & 0 & 0 & 0\end{pmatrix}\)

Exercice 4 : Donner le plus court chemin dans un graphe

On considère le graphe non orienté ci-dessous.

On donne également sa matrice associée. \[\begin{pmatrix}0 & 6 & 5 & 0 & 7 & 0 & 5\\6 & 0 & 0 & 4 & 3 & 7 & 0\\5 & 0 & 0 & 4 & 0 & 0 & 0\\0 & 4 & 4 & 0 & 8 & 0 & 6\\7 & 3 & 0 & 8 & 0 & 7 & 0\\0 & 7 & 0 & 0 & 7 & 0 & 0\\5 & 0 & 0 & 6 & 0 & 0 & 0\end{pmatrix}\]Donner le plus court chemin reliant C à E.
On donnera une réponse de la forme : \(A-B-C\)
Quelle est la longueur de ce chemin ?

Exercice 5 : Distance entre deux sommets d'un graphe orienté.

On considère le graphe orienté ci-dessous.


Déterminer la distance du sommet \(A\) au sommet \(D\).

Revenir au choix du niveau
False